iT邦幫忙

2026 iThome 鐵人賽

DAY 5
0
Software Development

30天刷完leetcoode75系列 第 5

C++ 演算法練習 Day5|1679, 643, 1456 題解與思路分享

  • 分享至 

  • xImage
  •  

https://ithelp.ithome.com.tw/upload/images/20260919/20184265nSGJRFRym3.png

題目解析:給定一個整數陣列與整數 k,每次可從陣列中挑選兩個總和為 k 的數字並移除,求最多能執行幾次這項操作
解題思路:先將陣列進行排序,然後設定左右兩個指標 i 和 j 分別從頭尾向中間尋找。如果相加等於 k,操作次數加一,並將兩邊指標同時往內縮;如果大於 k,代表右邊數字太大,將右指標往左移;如果小於 k,則將左指標往右移,直到兩指標交會,最後回傳操作次數。

class Solution {
public:
    int maxOperations(vector<int>& nums, int k) {
        int ans = 0, i = 0, j = nums.size()-1;
        sort(nums.begin(), nums.end());

        while(i < j){
            if(nums[i] + nums[j] == k){
                ans++, i++, j--;
            }else if(nums[i] + nums[j] > k){
                j--;
            }else{
                i++;
            }
        }

        return ans;
    }
};

https://ithelp.ithome.com.tw/upload/images/20260919/20184265iqJqQam7Bl.png

題目解析:給定一個陣列跟整數 k,找出長度為 k 的連續子陣列,使其元素總和最大,並回傳該最大平均值
解題思路:這題屬於滑動視窗(Sliding Window)的題型。先計算前 k 個數字的總和,接著將視窗往右推,每次減去視窗最前面的數字並加上新進來的數字,比較並記錄下最大的總和,最後回傳最大總和除以 k 所得的平均值。

class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        int q = 0;
        double ans;
        for(int i=0; i<k; i++){
            q += nums[i];
        }
        ans = q;

        for(int i=k; i<nums.size(); i++){
            q -= nums[i-k];
            q += nums[i];
            ans = max(ans, (double)q);
        }

        return ans / k;
    }
};

https://ithelp.ithome.com.tw/upload/images/20260919/20184265aSh8gX6yYg.png

題目解析:在一個字串中,找出長度為 k 的子字串,並求出該子字串中包含最多母音字母的數量(Maximum Number of Vowels in a Substring of Given Length)。
解題思路:同樣利用滑動視窗的概念。先用 set 建立一個母音集合,接著計算前 k 個字元中的母音數量。然後讓視窗開始往右滑動,每次判斷新加入的字元是否為母音以增加計數,同時判斷移出視窗的字元是否為母音以減少計數,過程中不斷更新最大值,最後回傳結果。

class Solution {
public:
    int maxVowels(string s, int k) {
        set<char> v{'a','e','i','o','u'};
        int ans, q = 0;
        for(int i=0; i<k; i++){
            if(v.count(s[i])) q++;
        }

        ans = q;
        for(int i=k; i<s.size(); i++){
            if(v.count(s[i])) q++;
            if(v.count(s[i-k])) q--;
            ans = max(ans, q);
        }

        return ans;
    }
};

上一篇
C++ 演算法練習 Day4|283, 392, 11 題解與思路分享
下一篇
C++ 演算法練習 Day6|1004, 1493, 1732題解與思路分享
系列文
30天刷完leetcoode756
圖片
  熱門推薦
圖片
{{ item.channelVendor }} | {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

1 則留言

0
godlichen
iT邦新手 5 級 ‧ 2026-09-20 03:24:14

十分讚的解法

我要留言

立即登入留言